/******************************************************************************
 * Compilation: javac MultiwayMinPQ.java
 * Execution:
 * <p/>
 * A multiway heap.
 ******************************************************************************/

package edu.princeton.cs.algs4;

import java.util.Iterator;
import java.util.Comparator;
import java.util.NoSuchElementException;

/**
 *  The MultiwayMinPQ class represents a priority queue of generic keys.
 *  It supports the usual insert and delete-the-minimum operations.
 *  It also supports methods for peeking at the minimum key,
 *  testing if the priority queue is empty, and iterating through
 *  the keys.
 *  It is possible to build the priority queue using a Comparator.
 *  If not, the natural order relation between the keys will be used.
 *
 *  This implementation uses a multiway heap.
 *  For simplified notations, logarithm in base d will be referred as log-d
 *  The delete-the-minimum operation takes time proportional to d*log-d(n)
 *  The insert takes time proportional to log-d(n)
 *  The is-empty, min-key and size operations take constant time.
 *  Constructor takes time proportional to the specified capacity.
 *
 *  @author Tristan Claverie
 */
public class MultiwayMinPQ<Key> implements Iterable<Key> {
    private final int d;                //Dimension of the heap
    private int n;                        //Number of keys currently in the heap
    private int order;                    //Number of levels of the tree
    private Key[] keys;                    //Array of keys
    private final Comparator<Key> comp;    //Comparator over the keys


    /**
     * Initializes an empty priority queue
     * Worst case is O(d)
     * @param D dimension of the heap
     * @throws IllegalArgumentException if D < 2
     */
    public MultiwayMinPQ(int D) {
        if (D < 2) throw new IllegalArgumentException("Dimension should be 2 or over");
        this.d = D;
        order = 1;
        keys = (Key[]) new Comparable[D << 1];
        comp = new MyComparator();
    }

    /**
     * Initializes an empty priority queue
     * Worst case is O(d)
     * @param D dimension of the heap
     * @param C a Comparator over the keys
     * @throws IllegalArgumentException if D < 2
     */
    public MultiwayMinPQ(Comparator<Key> C, int D) {
        if (D < 2) throw new IllegalArgumentException("Dimension should be 2 or over");
        this.d = D;
        order = 1;
        keys = (Key[]) new Comparable[D << 1];
        comp = C;
    }

    /**
     * Initializes a priority queue with given indexes
     * Worst case is O(n*log-d(n))
     * @param D dimension of the heap
     * @param a an array of keys
     * @throws IllegalArgumentException if D < 2
     */
    public MultiwayMinPQ(Key[] a, int D) {
        if (D < 2) throw new IllegalArgumentException("Dimension should be 2 or over");
        this.d = D;
        order = 1;
        keys = (Key[]) new Comparable[D << 1];
        comp = new MyComparator();
        for (Key k : a) insert(k);
    }

    /**
     * Initializes a priority queue with given indexes
     * Worst case is O(a*log-d(n))
     * @param D dimension of the heap
     * @param C a Comparator over the keys
     * @param a an array of keys
     * @throws IllegalArgumentException if D < 2
     */
    public MultiwayMinPQ(Comparator<Key> C, Key[] a, int D) {
        if (D < 2) throw new IllegalArgumentException("Dimension should be 2 or over");
        this.d = D;
        order = 1;
        keys = (Key[]) new Comparable[D << 1];
        comp = C;
        for (Key k : a) insert(k);
    }

    /**
     * Whether the priority queue is empty
     * Worst case is O(1)
     * @return true if the priority queue is empty, false if not
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * Number of elements currently on the priority queue
     * Worst case is O(1)
     * @return the number of elements on the priority queue
     */
    public int size() {
        return n;
    }

    /**
     * Puts a Key on the priority queue
     * Worst case is O(log-d(n))
     * @param key a Key
     */
    public void insert(Key key) {
        keys[n + d] = key;
        swim(n++);
        if (n == keys.length - d) {
            resize(getN(order + 1) + d);
            order++;
        }
    }

    /**
     * Gets the minimum key currently in the queue
     * Worst case is O(1)
     * @throws NoSuchElementException if the priority queue is empty
     * @return the minimum key currently in the priority queue
     */
    public Key minKey() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue is empty");
        return keys[d];
    }

    /**
     * Deletes the minimum key
     * Worst case is O(d*log-d(n))
     * @throws NoSuchElementException if the priority queue is empty
     * @return the minimum key
     */
    public Key delMin() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue is empty");
        exch(0, --n);
        sink(0);
        Key min = keys[n + d];
        keys[n + d] = null;
        int number = getN(order - 2);
        if (order > 1 && n == number) {
            resize(number + (int) Math.pow(d, order - 1) + d);
            order--;
        }
        return min;
    }

    /***************************
     * General helper functions
     **************************/

    //Compares two keys
    private boolean greater(int x, int y) {
        int i = x + d, j = y + d;
        if (keys[i] == null) return false;
        if (keys[j] == null) return true;
        return comp.compare(keys[i], keys[j]) > 0;
    }

    //Exchanges the position of two keys
    private void exch(int x, int y) {
        int i = x + d, j = y + d;
        Key swap = keys[i];
        keys[i] = keys[j];
        keys[j] = swap;
    }

    //Gets the maximum number of keys in the heap, given the number of levels of the tree
    private int getN(int order) {
        return (1 - ((int) Math.pow(d, order + 1))) / (1 - d);
    }

    /***************************
     * Functions for moving upward or downward
     **************************/

    //Moves upward
    private void swim(int i) {
        if (i > 0 && greater((i - 1) / d, i)) {
            exch(i, (i - 1) / d);
            swim((i - 1) / d);
        }
    }

    //Moves downward
    private void sink(int i) {
        int child = d * i + 1;
        if (child >= n) return;
        int min = minChild(i);
        while (min < n && greater(i, min)) {
            exch(i, min);
            i = min;
            min = minChild(i);
        }
    }

    /***************************
     * Deletes the minimum child
     **************************/

    //Return the minimum child of i
    private int minChild(int i) {
        int loBound = d * i + 1, hiBound = d * i + d;
        int min = loBound;
        for (int cur = loBound; cur <= hiBound; cur++) {
            if (cur < n && greater(min, cur)) min = cur;
        }
        return min;
    }

    /***************************
     * Resize the priority queue
     **************************/

    //Resizes the array containing the keys
    //If the heap is full, it adds one floor
    //If the heap has two floors empty, it removes one
    private void resize(int N) {
        Key[] array = (Key[]) new Comparable[N];
        for (int i = 0; i < Math.min(keys.length, array.length); i++) {
            array[i] = keys[i];
            keys[i] = null;
        }
        keys = array;
    }

    /***************************
     * Iterator
     **************************/

    /**
     * Gets an Iterator over the keys in the priority queue in ascending order
     * The Iterator does not implement the remove() method
     * iterator() : Worst case is O(n)
     * next() : 	Worst case is O(d*log-d(n))
     * hasNext() : 	Worst case is O(1)
     * @return an Iterator over the keys in the priority queue in ascending order
     */

    public Iterator<Key> iterator() {
        return new MyIterator();
    }

    //Constructs an Iterator over the keys in linear time
    private class MyIterator implements Iterator<Key> {
        MultiwayMinPQ<Key> data;

        public MyIterator() {
            data = new MultiwayMinPQ<Key>(comp, d);
            data.keys = (Key[]) new Comparable[keys.length];
            data.n = n;
            for (int i = 0; i < keys.length; i++) {
                data.keys[i] = keys[i];
            }
        }

        public boolean hasNext() {
            return !data.isEmpty();
        }

        public Key next() {
            return data.delMin();
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    /***************************
     * Comparator
     **************************/

    //default Comparator
    private class MyComparator implements Comparator<Key> {
        @Override
        public int compare(Key key1, Key key2) {
            return ((Comparable<Key>) key1).compareTo(key2);
        }
    }

}

/******************************************************************************
 *  Copyright 2002-2015, Robert Sedgewick and Kevin Wayne.
 *
 *  This file is part of algs4.jar, which accompanies the textbook
 *
 *      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
 *      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
 *      http://algs4.cs.princeton.edu
 *
 *
 *  algs4.jar is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  algs4.jar is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
 ******************************************************************************/
